package com.leecode.xiehf.page_02;

import com.leecode.Printer;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
 *
 * 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/insert-interval
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_0057 extends Printer {

    public static void main(String[] args) {
        Solution_0057 solution = new Solution_0057();
        int[][] intervals = {{1,2},{3,5},{6,7},{8,10},{12,16}};
//        int[][] intervals = {{1, 5}};
//        int[][] intervals = {{2, 3}, {4, 5}, {6, 7}, {1, 10}};
        int[][] s = solution.insert(intervals, new int[]{1, 5});
        print(s);
    }

    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0) {
            return new int[][]{newInterval};
        }
        List<int[]> list = new ArrayList<>();
        int i = 0;
        for (; i < intervals.length; i++) {
            int[] interval = intervals[i];
            if (interval[0] > newInterval[1]) {
                break;
            }
            if (interval[1] < newInterval[0]) {
                list.add(interval);
                continue;
            }
            if (interval[0] == newInterval[0] && interval[1] == newInterval[1]) {
                i++;
                break;
            } else if (interval[0] <= newInterval[1] && newInterval[0] <= interval[1]) {
                newInterval[0] = Math.min(interval[0], newInterval[0]);
                newInterval[1] = Math.max(interval[1], newInterval[1]);
            }
        }
        list.add(newInterval);
        for (; i < intervals.length; i++) {
            list.add(intervals[i]);
        }
        return list.toArray(new int[list.size()][2]);
    }
}
